package com.fx.algorithm.first;

import java.util.StringJoiner;

/**
 *  双端队列
 * @author fx
 */
public class MyCircularDeque {

    private final MyDoubleLinked list = new MyDoubleLinked();

    private final int capacity;

    /**
     * 构造函数,双端队列最大为 k
     */
    public MyCircularDeque(int k) {
        k = Math.min(Math.max(k,1),1000);
        this.capacity = k;
    }

    /**
     * 将一个元素添加到双端队列头部
     * @param value 插入元素
     * @return 如果操作成功返回 true ，否则返回 false
     */
    public boolean insertFront(int value) {
        if (isFull()) {
            return false;
        }
        list.insertFront(value);
        return true;
    }

    /**
     * 将一个元素添加到双端队列尾部。
     * @param value 插入元素
     * @return 如果操作成功返回 true ，否则返回 false
     */
    public boolean insertLast(int value) {
        if (isFull()) {
            return false;
        }

        list.insertLast(value);
        return true;
    }

    /**
     * 从双端队列头部删除一个元素。
     * @return 如果操作成功返回 true ，否则返回 false
     */
    public boolean deleteFront() {
        if (isEmpty()) {
            return false;
        }
        return list.deleteFront();
    }

    /**
     * 从双端队列尾部删除一个元素。
     * @return 如果操作成功返回 true ，否则返回 false
     */
    public boolean deleteLast() {
        if (isEmpty()) {
            return false;
        }
        return list.deleteLast();
    }

    /**
     *从双端队列头部获得一个元素。
     * @return 如果双端队列为空，返回 -1
     */
    public int getFront() {

        return list.getFront();
    }

    /**
     * 获得双端队列的最后一个元素
     * @return  如果双端队列为空，返回 -1
     */
    public int getRear() {

        return list.getRear();
    }

    /**
     * 队列是否为空
     * @return 若双端队列为空，则返回 true ，否则返回 false
     */
    public boolean isEmpty() {

        return list.size==0;
    }

    /**
     *  队列是否满了
     * @return 若双端队列满了，则返回 true ，否则返回 false
     */
    public boolean isFull() {

        return list.size >= capacity;
    }


    public static class MyDoubleLinked{

        private final Node head = new Node(-1);

        private final Node tail = new Node(-1);

        private int size;


        public void insertFront(int v) {
            Node newNode = new Node(v);
            Node next = head.next;
            if (next == null) {
                head.next = newNode;
                newNode.next=tail;
                tail.pre = newNode;
                newNode.pre = head;
            }else{
                head.next = newNode;
                newNode.next = next;
                next.pre = newNode;
                newNode.pre = head;
            }
            size++;
        }

        public void insertLast(int v) {
            Node newNode = new Node(v);
            Node last = tail.pre;
            if (last == null) {
                tail.pre =newNode;
                head.next = newNode;
                newNode.next = tail;
                newNode.pre = head;
            }else {
                last.next = newNode;
                newNode.next = tail;
                tail.pre =newNode;
                newNode.pre = last;
            }
            size++;

        }

        public boolean deleteFront() {
            Node headNode = head.next;
            if (headNode != null) {
                head.next = headNode.next;
                head.next.pre = head;
                size--;
                return true;
            }
            return false;
        }

        public boolean  deleteLast() {
            Node laseNode = tail.pre;
            if (laseNode != null) {
                tail.pre = laseNode.pre;
                tail.pre.next = tail;
                size--;
                return true;
            }
            return false;
        }

        public int getFront() {
            Node headNode = head.next;
            if (headNode != null) {
                return headNode.v;
            }
            return -1;
        }

        public int getRear() {
            Node laseNode = tail.pre;
            if (laseNode != null) {
                return laseNode.v;
            }
            return -1;
        }

        @Override
        public String toString() {
            StringJoiner joiner = new StringJoiner(",", "[", "]");
            Node node = head.next;
            while (node != null&&node.v!=-1) {
                joiner.add(String.valueOf(node.v));
                node = node.next;
            }
            return joiner.toString();
        }
    }

    public static void main(String[] args) {
        //MyDoubleLinked doubleLinked = new MyDoubleLinked();
        //doubleLinked.insertFront(4);
        //doubleLinked.insertFront(9);
        //doubleLinked.insertFront(3);
        //doubleLinked.insertLast(2);
        ////System.err.println(doubleLinked);
        ////doubleLinked.deleteLast();
        ////
        ////System.err.println(doubleLinked);
        ////doubleLinked.deleteFront();
        ////System.err.println(doubleLinked);
        //
        //System.err.println(doubleLinked.getFront());
        //System.err.println(doubleLinked.getRear());

        MyCircularDeque deque = new MyCircularDeque(4);
        deque.insertFront(9);
        deque.deleteLast();
        System.err.println(deque.getRear());
        System.err.println(deque.getFront());
        System.err.println(deque.getFront());
        deque.deleteFront();

    }


    public static class Node{

        private Node pre;

        private int v =-1;

        private Node next;

        public Node(Node p, int v, Node n) {
            this.pre = p;
            this.v = v;
            this.next = n;
        }

        public Node(int v) {
            this.v = v;
        }

    }
}
